package zuoshen.chapter1;

import java.util.Stack;

//仅使用递归，逆序一个栈
public class InverseStack {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        inverseStack(stack);
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

    //总体思路：每次获取当前栈底元素，暂存到当前递归栈，继续递归，等返回到当前递归栈时把暂存的元素入栈
    //复杂度在每次获取栈底元素的操作上，n+(n-1)+...+1=n(n+1)/2，即O(n^2)
    public static void inverseStack(Stack<Integer> stack){
        if(stack.isEmpty()) return;
        int last = getAndRemoveLastElem(stack);
        inverseStack(stack);
        //放回
        stack.push(last);
    }

    //得到栈底元素
    public static int getAndRemoveLastElem(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.isEmpty()) return result;
        //继续递归得到栈底
        int last = getAndRemoveLastElem(stack);
        //回填
        stack.push(result);
        return last;
    }
}
